#include <iostream>
#include <vector>

using namespace std;

class Solution 
{
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
    {
        vector<int> last;
        int j1 = 0, j2 = 0;
        while (j1 < m || j2 < n)
        {
            if (j1 == m)
            {
                last.emplace_back(nums2[j2++]);
            }
            else if (j2 == n)
            {
                last.emplace_back(nums1[j1++]);
            }
            else if (nums1[j1] < nums2[j2])
            {
                last.emplace_back(nums1[j1++]);
            }
            else
            {
                last.emplace_back(nums2[j2++]);
            }
        }
        swap(last, nums1);
    }
};

int main()
{
    vector<int> nums1{ 1, 2, 3, 0, 0, 0 }; 
    int m = 3;
    vector<int> nums2{ 2, 5, 6 };
    int n = 3;

    Solution xz;
    xz.merge(nums1, m, nums2, n);
    for (auto e : nums1)
    {
        cout << e << " ";
    }

	return 0;
}
